//BZOJ 2242
#include <bits/stdc++.h>

using namespace std;

int p;

int qpow(int base,int exp){
    int ans=1;
    while(exp){
        if(exp&1) ans=((long long)ans*base)%p;
        base=((long long)base*base)%p;
        exp>>=1;
    }
    return ans;
}

int exgcd(int a,int b,int &x,int &y){
    if(b){
        int ans=exgcd(b,a%b,x,y);
        int t=x;
        x=y;y=t-a/b*y;
        return ans;
    }else{
        x=1;y=0;
        return a;
    }
}

bool solvEqu(int a,int b,int c,int &x,int &y){
    int g;
    g=exgcd(a,b,x,y);
    if(c%g) return false;
    x=(long long)x*c/g%p;y=(long long)y*c/g%p;
    return true;
}

int inv(int a,int c=1){
    int x,y;
    if(solvEqu(a,p,c,x,y)){
        return (x%p+p)%p;
    }else return -1;
}

int bsgs(int a,int c){
    a%=p;
    int m=ceil(sqrt(p));
    int t,q;
    if(a==0&&c==0) return 1;
    else if(a==0) return -1;
    map<int,int> ha;
    ha[t=1]=0;
    for(int i=1;i<m;i++) if(!ha.count(t=(long long)t*a%p)) ha[t]=i;
    t=qpow(a,p-m-1);
    q=c%p;
    for(int k=0;k<=m;k++){
        if(ha.count(q)) return k*m+ha[q];
        q=(long long)q*t%p;
    }
    return -1;
}

const char *notfound="Orz, I cannot find x!\n";

inline int read(){
    int r;char c;bool f=0;
    for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') f=1;
    for(r=0;c<='9'&&c>='0';c=getchar()) r=r*10+c-'0';
    if(f) return -r;
    else return r;
}

int main(){
    int T,k;
    T=read();k=read();
    while(T--){
        int y,z,ans;
        y=read();z=read();p=read();
        if(k==1) printf("%d\n",qpow(y,z));
        else if(k==2)
            if((ans=inv(y,z))!=-1) printf("%d\n",ans);
            else printf(notfound);
        else
            if((ans=bsgs(y,z))!=-1) printf("%d\n",ans);
            else printf(notfound);
    }
    return 0;
}
